#include "AKCommon.h"
#include "CDSQTTHHEngine.h"
#include "CDSQBoard.h"

#include <stdlib.h>
#include <time.h>
#include <memory.h>

void CDSQTTHHEngine::backToInitialState()
{
	CAlgSearchEngine::backToInitialState();
	InitializeHashKey();
	times = 0;
}

void CDSQTTHHEngine::RunSearchEngine(CDSQBoard* pBoard, AKSideIndex side)
{
	//int i,j,pointer;
	
	//default moves
	if( times == 0 )
	{
		if( side == Right )
		{
			// right elephant moves upward
			m_best.From.x = 6;
			m_best.From.y = 6;
			m_best.To.x = 6;
			m_best.To.y = 5;
		}
		else
		{
			// left elephant moves upward
			m_best.From.x = 2;
			m_best.From.y = 6;
			m_best.To.x = 3;
			m_best.To.y = 6;
		}
		times++;
	}
	else if( times == 1 )
	{
		if( side == Right )
		{
			// right rat moves forward
			m_best.From.x = 6;
			m_best.From.y = 0;
			m_best.To.x = 5;
			m_best.To.y = 0;
		}
		else
		{
			// left rat moves forward
			m_best.From.x = 2;
			m_best.From.y = 0;
			m_best.To.x = 2;
			m_best.To.y = 1;
		}
		times++;
	}
	else
	{
		//reset the bestmove-buffer
		m_best.From.x = 0;
		m_best.From.y = 0;
		m_best.To.x = 0;
		m_best.To.y = 0;
		
		CalculateInitHashKey(pBoard->m_CurPosition);			//calculate the Hash-keys
		TTHHAlphaBeta( pBoard, m_depth, -20000, 20000, side );	//advanced searching
	}
	
	PARENT::m_BestMove.piece	= pBoard->m_CurPosition[m_best.From.y][m_best.From.x];
	PARENT::m_BestMove.side		= side;
	PARENT::m_BestMove.srcCell  = m_best.From.y * 9 + m_best.From.x;
	PARENT::m_BestMove.dstCell  = m_best.To.y * 9 + m_best.To.x;

	/*if (HistoryCount < 6)
	{
		m_cmHistoryMove[HistoryCount] = m_cmBestMove;
	}
	else
	{
		pointer = HistoryCount % 6;
		i = pointer - 2;
		j = pointer - 4;
		if( i<0 )
			i += 6;
		if( j<0 )
			j += 6;
		
		/********determin if the move has repeated********/
		/*if( m_cmBestMove.From.x == m_cmHistoryMove[i].From.x &&
		   m_cmBestMove.From.y == m_cmHistoryMove[i].From.y &&
		   m_cmBestMove.To.x == m_cmHistoryMove[i].To.x &&
		   m_cmBestMove.To.y == m_cmHistoryMove[i].To.y &&
		   m_cmHistoryMove[i].From.x == m_cmHistoryMove[j].From.x &&
		   m_cmHistoryMove[i].From.y == m_cmHistoryMove[j].From.y &&
		   m_cmHistoryMove[i].To.x == m_cmHistoryMove[j].To.x &&
		   m_cmHistoryMove[i].To.y == m_cmHistoryMove[j].To.y )
		{
			m_cmBestMove = m_cmBetterMove;
			hasAlternative = false;
		}
		
		m_cmHistoryMove[pointer] = m_cmBestMove;
	}*/
	
	//HistoryCount++;
}

int CDSQTTHHEngine::TTHHAlphaBeta(CDSQBoard* pBoard, unsigned int depth, int alpha, int beta, AKSideIndex side)
{
	int score;
	int Count,i;
	AKSideIndex _side;
	unsigned char type;
	
	i = pBoard->IsGameOver(depth, side);
	if (i != 0)
		return i;
	
	// get the current side
	if (side == Left)
		_side = !((m_depth - depth) & 0x1);
	if (side == Right)
		_side = ( m_depth-depth ) & 0x1;
	
	// if we have encounter the transposition before, return the value calculated previously.
	score = LookUpHashTable( alpha, beta, depth, _side );
	if (score != 200000)
		return score;
	
	if (depth <= 0)	//get the value at the leaf-node
	{
		score = pBoard->Evaluate( _side );
		EnterHashTable( EntryTypeExact, score, depth, _side );
		return score;
	}
	
	pBoard->CreatePossibleMove( depth, _side );
	Count = pBoard->m_PossibleMovementCounter;
	
	int eval_is_exact = 0;
	
	for (i = 0; i < Count; i++ )
		pBoard->m_MoveList[depth][i].Score = GetHistoryScore( &(pBoard->m_MoveList[depth][i]) );
	
	MergeSort(pBoard->m_MoveList[depth], Count, 0);
	
	int bestmove = -1;	//remember the best-move
	
	for (i = 0; i < Count; i++ )
	{
		Hash_MakeMove( &(pBoard->m_MoveList[depth][i]), pBoard->m_CurPosition );
		type = pBoard->MakeMove( &(pBoard->m_MoveList[depth][i]) );

		score = -TTHHAlphaBeta(pBoard, depth-1, -beta, -alpha, side);

		Hash_UnMakeMove( &(pBoard->m_MoveList[depth][i]), type, pBoard->m_CurPosition );
		pBoard->UnMakeMove( &(pBoard->m_MoveList[depth][i]), type );
		
		if (score >= beta)	//beta pruning
		{
			EnterHashTable(EntryTypeLowerBound,score,depth,_side);	// save the lower bound of the node to the transposition table
            return score;
        }
		if (score > alpha)
		{
			alpha=score;
			eval_is_exact = 1;
			if (depth == m_depth)
			{
				m_best = pBoard->m_MoveList[depth][i];
			}
			bestmove = i;
		}
        if (alpha >= beta)
		{
			bestmove = i;
			break;
		}
	}
	
	if (eval_is_exact)
		EnterHashTable( EntryTypeExact, alpha, depth, _side );
    else
		EnterHashTable( EntryTypeUpperBound, alpha, depth, _side );
	if (bestmove != -1)
		EnterHistoryScore( &(pBoard->m_MoveList[depth][bestmove]), depth );	//add the best-move to the history-talbe
	
	return alpha;
}

/******************HistoryHeuristic Engine********************/

void CDSQTTHHEngine::ResetHistoryTable()
{
	memset(m_HistoryTable, 0, 4900*sizeof(int));
}

int CDSQTTHHEngine::GetHistoryScore(PieceMove *move)
{
	int nFrom,nTo;
	
	nFrom=move->From.y*10+move->From.x;	// origigal position
	nTo=move->To.y*10+move->To.x;		// destination position
	
	return m_HistoryTable[nFrom][nTo];	// return the historical score
}

void CDSQTTHHEngine::EnterHistoryScore(PieceMove *move, int depth)
{
	int nFrom,nTo;
	
	nFrom=move->From.y*10+move->From.x;	// original position
	nTo=move->To.y*10+move->To.x;		// destination position
	
	m_HistoryTable[nFrom][nTo] += 2<<depth;	// increase the historical score by pow(2, depth)
}

void CDSQTTHHEngine::MergeSort(PieceMove *source, int n, int direction)
{
	int s=1;
	
	while(s<n)
	{
		MergePass(source,m_TargetBuff,s,n,direction);
		s+=s;
		MergePass(m_TargetBuff,source,s,n,direction);
		s+=s;
	}
}

void CDSQTTHHEngine::Merge(PieceMove *source, PieceMove *target, int l, int m, int r)
{
	// ascending order
	int i=l;
	int j=m+1;
	int k=l;
	int q;
	
	while(i<=m && j<=r)
		if(source[i].Score<=source[j].Score)
			target[k++]=source[i++];
		else
			target[k++]=source[j++];
	
	if(i>m)
		for(q=j; q<=r;q++)
			target[k++]=source[q];
	else
		for(q=i; q<=m;q++)
			target[k++]=source[q];
}

void CDSQTTHHEngine::MergePass(PieceMove *source, PieceMove *target, const int s, const int n, const int direction)
{
	int i=0;
	int j;
	
	while(i<=n-2*s)
	{
		if(direction)
			Merge(source,target,i,i+s-1,i+2*s-1);
		else
			Merge_A(source,target,i,i+s-1,i+2*s-1);
		i=i+2*s;
	}
	
	if(i+s<n)
	{
		if(direction)
			Merge(source,target,i,i+s-1,n-1);
		else
			Merge_A(source,target,i,i+s-1,n-1);
	}
	else
		for(j=i;j<=n-1;j++)
			target[j]=source[j];
}

void CDSQTTHHEngine::Merge_A(PieceMove *source, PieceMove *target, int l, int m, int r)
{
	// descending order
	int i=l;
	int j=m+1;
	int k=l;
	int q;
	
	while(i<=m && j<=r)
		if(source[i].Score>=source[j].Score)
			target[k++]=source[i++];
		else
			target[k++]=source[j++];
	
	if(i>m)
		for(q=j;q<=r;q++)
			target[k++]=source[q];
	else
		for(q=i;q<=m;q++)
			target[k++]=source[q];
}

/***************TranspositionTable*****************/

void CDSQTTHHEngine::CalculateInitHashKey(PieceIndex CurPosition[][9])
{
	int j,k,nChessType;
	
	m_HashKey32 = 0;
	m_HashKey32 = 0;
	
	for(j=0; j<7; j++)
		for(k=0; k<9; k++)
		{
			nChessType = CurPosition[j][k];
			if(nChessType != NOCHESS)
			{
				m_HashKey32 = m_HashKey32 ^ m_nHashKey32[nChessType][j][k];
				m_HashKey64 = m_HashKey64 ^ m_ulHashKey64[nChessType][j][k];
			}
		}
}

void CDSQTTHHEngine::Hash_MakeMove(PieceMove *move, PieceIndex CurPosition[][9])
{
	PieceIndex nToID,nFromID;
	
	nFromID = CurPosition[move->From.y][move->From.x];
	nToID = CurPosition[move->To.y][move->To.x];
	
	m_HashKey32=m_HashKey32^m_nHashKey32[nFromID][move->From.y][move->From.x];
	m_HashKey64=m_HashKey64^m_ulHashKey64[nFromID][move->From.y][move->From.x];
	
	if(nToID!=NOCHESS)
	{
		m_HashKey32=m_HashKey32^m_nHashKey32[nToID][move->To.y][move->To.x];
		m_HashKey64=m_HashKey64^m_ulHashKey64[nToID][move->To.y][move->To.x];
	}
	
	m_HashKey32=m_HashKey32^m_nHashKey32[nFromID][move->To.y][move->To.x];
	m_HashKey64=m_HashKey64^m_ulHashKey64[nFromID][move->To.y][move->To.x];
}

void CDSQTTHHEngine::Hash_UnMakeMove(PieceMove *move, unsigned int nChessID, PieceIndex CurPosition[][9])
{
	PieceIndex nToID;
	
	nToID=CurPosition[move->To.y][move->To.x];
	
	m_HashKey32=m_HashKey32^m_nHashKey32[nToID][move->From.y][move->From.x];
	m_HashKey64=m_HashKey64^m_ulHashKey64[nToID][move->From.y][move->From.x];
	
	m_HashKey32=m_HashKey32^m_nHashKey32[nToID][move->To.y][move->To.x];
	m_HashKey64=m_HashKey64^m_ulHashKey64[nToID][move->To.y][move->To.x];
	
	if(nChessID)
	{
		m_HashKey32=m_HashKey32^m_nHashKey32[nChessID][move->To.y][move->To.x];
		m_HashKey64=m_HashKey64^m_ulHashKey64[nChessID][move->To.y][move->To.x];
	}
}

int CDSQTTHHEngine::LookUpHashTable(int alpha, int beta, int depth, int sideNo)
{
	int x;
	HashItem* pht;
	
	x = m_HashKey32 & 0xFFFFF;
	pht = &m_pTT[sideNo][x];
	
    if(pht->depth >= depth && pht->checksum == m_HashKey64)
	{
		switch(pht->entry_type)
		{
			case EntryTypeExact:
				return pht->eval;
			case EntryTypeLowerBound:
				if(pht->eval >= beta)
					return pht->eval;
				break;
			case EntryTypeUpperBound:
				if (pht->eval <= alpha)
					return pht->eval;
				break;
        }
	}
	
	return 200000;	// indicate the transposition hasn't been encountered before 
}

void CDSQTTHHEngine::EnterHashTable(EntryType entry_type, short eval, short depth, int TableNo)
{
	int x;
	HashItem* pht;
	
	x = m_HashKey32 & 0xFFFFF;	// calculate 20 bits hash address
	pht=&m_pTT[TableNo][x];
	
	pht->checksum	= m_HashKey64;
	pht->entry_type = entry_type;
	pht->eval		= eval;
	pht->depth		= depth;
}

void CDSQTTHHEngine::InitializeHashKey()
{
	int i,j,k;
	
	srand((unsigned)time(NULL));
	
	for (i=0; i<17; i++) 
	{
		for (j=0; j<7; j++) 
		{
			for (k=0; k<9; k++)
			{
				m_nHashKey32[i][j][k]=Rand32();
				m_ulHashKey64[i][j][k]=Rand64();
			}
		}
	}
	
	m_pTT[0]=(HashItem*)malloc(1024*1024*sizeof(HashItem));	// for storing maximum values of nodes
	m_pTT[1]=(HashItem*)malloc(1024*1024*sizeof(HashItem));	// for storing minimum values of nodes
}

// generate 64 bits random number
long long CDSQTTHHEngine::Rand64()
{
    return rand()^((long long)rand()<<15)^((long long)rand()<<30)^
	((long long)rand()<<45)^((long long)rand()<<60);
}

// generate 32 bits random number
int CDSQTTHHEngine::Rand32()
{
    return rand()^((int)rand()<<15)^((int)rand()<<30);
}